Heap堆——数据结构系列教程(c++版)

5.1 Entitys.h 头文件

#ifndef ENTITYS_H_INCLUDED
#define ENTITYS_H_INCLUDED

//************************************************************************************************************************************************************************
//                                                                      自定义类型
//************************************************************************************************************************************************************************

//========================================================================================================================================================================
//                                                                    学生结构体(Student)
//========================================================================================================================================================================
struct Student {
    int id;// 学号
    std::string name;// 姓名
    std::string dob;// 出生日期
    std::string sex;// 性别
    std::string gender;// 民族
    std::string address;// 地址
    float score;// 入学总分
    std::string school;// 学校
    std::string team;// 班级
    std::string status;// 状态

    bool operator<(const Student& other) const { return id < other.id; }
    bool operator>(const Student& other) const { return id > other.id; }
    bool operator==(const Student& other) const { return id == other.id; }
    bool operator!=(const Student& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const Student& s) {
        os << "[" << s.id<< ", " << s.name << ", " << s.dob << ", " << s.sex << ", " << s.gender  << ", " << s.address << ", " << s.score<< ", " << s.school<< ", " << s.team<< ", " << s.status << "]";
        return os;
    }
};

//========================================================================================================================================================================
//
//                                                                    学生索引结构体(Student)
//
//========================================================================================================================================================================
struct StudentIndex {
    int id;// 学号
    int row;// 行号

    bool operator<(const StudentIndex& other) const { return id < other.id; }
    bool operator>(const StudentIndex& other) const { return id > other.id; }
    bool operator==(const StudentIndex& other) const { return id == other.id; }
    bool operator!=(const StudentIndex& other) const { return id != other.id; }

    friend std::ostream& operator<<(std::ostream& os, const StudentIndex& i) {
        os << "[" << i.id << ", " << i.row<< "]";
        return os;
    }
};

//========================================================================================================================================================================
//                                                                    迷宫坐标结构体(Pos)
//========================================================================================================================================================================
struct Pos{
    int x;     //x坐标
    int y;    //y坐标
    int step; //步数
};

//========================================================================================================================================================================
//                                                                    打印任务结构体(PrintTask)
//========================================================================================================================================================================
struct PrintTask{
    int taskId;     // 任务ID
    char content[50]; // 打印内容
};

//========================================================================================================================================================================
//
//                                                                    哈夫曼树节点结构体(HuffmanNode)
//
//========================================================================================================================================================================
struct HuffmanNode {
    char ch;                // 字符（非叶子节点设为 '\0'）
    int freq;               // 频率
    HuffmanNode *left;      // 左子节点
    HuffmanNode *right;     // 右子节点

    bool operator<(const HuffmanNode& other) const { return freq < other.freq; }
    bool operator>(const HuffmanNode& other) const { return freq > other.freq; }
    bool operator==(const HuffmanNode& other) const { return freq == other.freq; }
    bool operator!=(const HuffmanNode& other) const { return freq != other.freq; }

    friend std::ostream& operator<<(std::ostream& os, const HuffmanNode* h) {
        os << "[" << h->ch << ", " << h->freq<< "]";
        return os;
    }
};

//========================================================================================================================================================================
//
//                                                                    使用指针类型时，传入自定义比较器
//
//========================================================================================================================================================================
struct HuffmanNodeCmp {
    bool operator()(HuffmanNode* a, HuffmanNode* b) {
        return a->freq < b->freq; // 比较节点权重
    }
};

//========================================================================================================================================================================
//
//                                                                    哈夫曼编码表结构体(CodeTable)
//
//========================================================================================================================================================================
struct CodeTable {
    char ch;
    char code[MAX_CODE_LEN];
};
            
            #endif // ENTITYS_H_INCLUDED
                    

5.2 ArrayHeap.h 头文件

#ifndef LINKEDBSTREE_H_INCLUDED
#define LINKEDBSTREE_H_INCLUDED

#include <iostream>
#include <vector>
#include <stdexcept>
#include <algorithm>
#include "Entitys.h"

//========================================================================================================================================================================
//
//                                                                 数组堆结构体(ArrayHeap)
//
//========================================================================================================================================================================
template <typename T, typename Compare = std::less<T>>
struct ArrayHeap{
    // ------------------------------------------------------------------------------------------------------
    //                                          私有成员
    // 注：私有成员只能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)不能访问调用）
    //------------------------------------------------------------------------------------------------------
    private:

        //---------------声明私有成员变量---------------

        std::vector<T> heap;  // 模板化堆元素，支持存储任意类型

        //---------------声明私有成员函数---------------

        int parent(int index);      // 获取父节点索引
        int leftChild(int index);   // 获取左子节点索引
        int rightChild(int index);  // 获取右子节点索引
        void swap(int i, int j);   // 交换两个元素
        void heapifyUp(int index);  // 向上堆化：维护最小堆性质（插入元素后调用）
        void heapifyDown(int index);// 向下堆化：维护最小堆性质（删除堆顶后调用）
        void buildHeap(std::vector<T>& arr);           // 批量构建堆的向下堆化

    // ------------------------------------------------------------------------------------------------------
    //                                          公共成员
    // 注：公共成员能在该结构体内部访问调用，外部通过该结构体定义(实例化)的变量(对象)也能访问调用）
    //------------------------------------------------------------------------------------------------------
    public:

        //---------------声明公共成员函数---------------

        // 构造函数：外部通过该结构体定义(实例化)变量(对象)时，自动执行该函数(主要用于初始化成员变量的值)
        ArrayHeap() {
        }

        // 用数组构建堆
        ArrayHeap(std::vector<T>& arr) {
            buildHeap(arr);             //批量构建堆的向下堆化
        }

        void put(const T& value);       // 入堆，插入元素到堆中
        std::vector<T> sort(int type); // 排序
        T get();                         // 出堆，删除并返回堆顶元素（最小值）
        T getMin();                      // 获取堆顶元素（最小值，不删除）
        int size();                     // 获取堆的大小
        bool isEmpty();                 // 判断堆是否为空
        void print();                   // 打印堆数据

        // 析构函数：自动销毁队列，避免内存泄漏
        ~ArrayHeap() {
        }
};

#endif // ARRAYHEAP_H_INCLUDED

5.3 ArrayHeap.cpp 程序代码

#include "ArrayHeap.h"
//---------------实现私有成员函数---------------

// 获取父节点索引
template <typename T, typename Compare>
int ArrayHeap<T,Compare>::parent(int index) {
    return (index - 1) / 2;
}

// 获取左子节点索引
template <typename T, typename Compare>
int ArrayHeap<T,Compare>::leftChild(int index) {
    return 2 * index + 1;
}

// 获取右子节点索引
template <typename T, typename Compare>
int ArrayHeap<T,Compare>::rightChild(int index) {
    return 2 * index + 2;
}

// 交换两个元素
template <typename T, typename Compare>
void ArrayHeap<T,Compare>::swap(int i, int j) {
    T temp = heap[i];
    heap[i] = heap[j];
    heap[j] = temp;
}

// 向上堆化：维护最小堆性质（插入元素后调用
template <typename T, typename Compare>
void ArrayHeap<T,Compare>::heapifyUp(int index) {
    // 非根节点，且当前节点 < 父节点 → 交换并继续向上调整
    //if (index > 0 && heap[index] < heap[parent(index)]) {
    if(index > 0 && cmp(heap[index], heap[parent(index)])) {
        swap(index, parent(index));
        heapifyUp(parent(index));  // 递归调整父节点
    }
}

// 向下堆化：维护最小堆性质（删除堆顶后调用）
template <typename T, typename Compare>
void ArrayHeap<T,Compare>::heapifyDown(int index) {
    int smallest = index;  // 初始化最小值索引为当前节点
    int left = leftChild(index);
    int right = rightChild(index);

    // 左子节点存在且更小 → 更新最小值索引
    //if (left < heap.size() && heap[left] < heap[smallest]) {
    if (left < heap.size() && cmp(heap[left],heap[smallest])) {
        smallest = left;
    }

    // 右子节点存在且更小 → 更新最小值索引
    //if (right < heap.size() && heap[right] < heap[smallest]) {
    if (right < heap.size() && cmp(heap[right],heap[smallest])) {
        smallest = right;
    }

    // 最小值不是当前节点 → 交换并递归调整子节点
    if (smallest != index) {
        swap(index, smallest);
        heapifyDown(smallest);
    }
}

//批量构建堆的向下堆化
template <typename T, typename Compare>
void ArrayHeap<T,Compare>::buildHeap(std::vector<T>& arr) {
    heap = arr;
    int startIdx = (heap.size() - 2) / 2;  // 最后一个非叶子节点
    for (int i = startIdx; i >= 0; --i) {
        heapifyDown(i); // 从下向上批量堆化
    }
}

//---------------实现公共成员函数---------------

// 入堆，插入元素到堆中
template <typename T, typename Compare>
void ArrayHeap<T,Compare>::put(const T& value) {
    heap.push_back(value);  // 元素添加到数组末尾
    heapifyUp(heap.size() - 1);  // 向上堆化最后一个元素
}

// 基于当前堆的元素，返回升序排序结果（不破坏原堆） 0 为升序 1 为降序
template <typename T, typename Compare>
std::vector<T> ArrayHeap<T,Compare>::sort(int type) {
    if (isEmpty()) {
        return {};
    }

    ArrayHeap tempHeap(heap);// 复制当前堆，避免破坏原堆结构
    std::vector<T> sortedArr;

    // 依次提取最小值，生成升序数组
    while (!tempHeap.isEmpty()) {
        sortedArr.push_back(tempHeap.get());
    }

    //降序
    if(type == 1)
    {
        reverse(sortedArr.begin(),sortedArr.end());	//进行反转
    }

    return sortedArr;
}

// 出堆，删除并返回堆顶元素（最小值）
template <typename T, typename Compare>
T ArrayHeap<T,Compare>::get() {
    if (isEmpty()) {
        throw std::runtime_error("Error: 无法从空堆中删除元素！");
    }

    T minValue = heap[0];  // 保存堆顶最小值
    // 堆只有一个元素时，直接弹出
    if (heap.size() == 1) {
        heap.pop_back();
        return minValue;
    }

    // 最后一个元素移到堆顶，然后删除最后一个元素
    heap[0] = heap.back();
    heap.pop_back();
    heapifyDown(0);  // 向下堆化堆顶元素

    return minValue;
}

// 获取堆顶元素（最小值，不删除）
template <typename T, typename Compare>
T ArrayHeap<T,Compare>::getMin() {
    if (isEmpty()) {
        throw std::runtime_error("Error: 堆为空，无堆顶元素！");
    }
    return heap[0];
}

// 获取堆的大小
template <typename T, typename Compare>
int ArrayHeap<T,Compare>::size() {
    return heap.size();
}

// 判断堆是否为空
template <typename T, typename Compare>
bool ArrayHeap<T,Compare>::isEmpty() {
    return heap.empty();
}

// 打印堆的所有元素
template <typename T, typename Compare>
void ArrayHeap<T,Compare>::print() {
    std::cout << "小根堆元素: ";
    for (T num : heap) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

// 显式实例化常用类型（避免链接错误，可选）
template class ArrayHeap<int>;
template class ArrayHeap<char>;
template class ArrayHeap<float>;
template class ArrayHeap<std::string>;
template class ArrayHeap<Student>;
template class ArrayHeap<HuffmanNode*>; 
template class ArrayHeap<HuffmanNode*, HuffmanNodeCmp>;

5.4 main.cpp 测试代码

#include <iostream>
#include <string>
#include "ArrayHeap.h"

int main() {   

    // 1. 插入'f','e','c','d','b','j','g','h','i','a'
    vector<char> arrayChar = {'f','e','c','d','b','j','g','h','i','a'};
    ArrayHeap<char> hape(arrayChar);//批量堆化
    hape.print();

    // 2. 排序
    vector<char> arrayAsc = hape.sort();
    cout << "升序排序: ";
    for(int i=0;i < arrayAsc.size();i++)
    {
        cout << arrayAsc[i] << " ";
    }
    cout << endl;

    // 3. 入堆 k
    cout << "入堆元素 : k" << endl;
    hape.put('k');
    hape.print();
    vector<char> arrayDesc = hape.sort();
    cout << "降序排序: ";
    for(int i=arrayDesc.size()-1;i>=0;i--)
    {
        cout << arrayDesc[i] << " ";
    }
    cout << endl;
    
    return 0;
}

输出结果

小根堆元素: a b c d e j g h i f
升序排序: a b c d e f g h i j
入堆元素 : k
小根堆元素: a b c d e j g h i f k
降序排序: k j i h g f e d c b a
    

六、注意事项

七、总结

堆是一种高效的优先队列实现，核心是利用完全二叉树的结构特性，通过向上堆化和向下堆化操作维护堆序性。其核心价值在于快速获取最值，在 Top-K、优先队列、多路归并等场景中不可或缺。

常见坑点与避坑经验

• 混淆堆的索引计算：牢记 “从 0 开始” 和 “从 1 开始” 的索引差异，若代码中索引计算错误，会直接导致堆操作失效。
• 构建堆的方法错误：避免对每个元素执行向上堆化，务必从最后一个非叶子节点向上堆化。
• 自定义类型未重载比较运算符：使用自定义结构体时，必须重载 < 或 > 运算符，或传入自定义比较函数。

本教程通过代码解析和实战示例，覆盖了堆的核心原理、关键操作实现和实际使用场景。掌握堆的原理和实现，区分不同场景下的堆类型选择，并通过实战（如手写堆、解决 Top-K 问题）加深理解。